#include <stdio.h>
#include <malloc.h>

#define MAXSIZE 100

//树：tree 二叉树
// binary tree:二叉树
// //binary serach tree :二叉搜索树/BST
//二叉链表来实现一个二叉树
typedef char ElementType;
//1.定义数据结构
typedef struct node{
    //1.数据项
    ElementType data;
    //2.地址项
    struct node* left;
    struct node* right;
} BTnode;
//2.实现操作
//1.创建节点
/*
 * 函数名：createBTnode()
 * 输入：存储元素
 * 输出：创建好的结点
 *
 * */


/*中序遍历过程：
（1）中序遍历左子树
（2）访问根节点
（3）中序遍历右子树*/
/*
 * 函数名：inOrder()
 * 输入：待遍历的二叉树
 * 输出：无
 * */
void inOrder(BTnode *tree){
    //树不为空，进行遍历
    if(tree){
        //（1）中序遍历左子树
        inOrder(tree->left);
       // （2）访问根节点
        printf(" %c",tree->data);
       // （3）中序遍历右子树
        inOrder(tree->right);
    }
}

BTnode *createBTnode(ElementType data){
    //1.分配空间
    BTnode *node=malloc(sizeof(BTnode));
    //2.初始化参数
    node->data=data;
    node->left=NULL;
    node->right=NULL;
    //返回
    return node;
}
//层序遍历
/*
 * 1.创建一个队列
 * 2.将树的根进队
 * 3.while(队不为空){
 *    3.1 出队（删除队首），并打印该结点的值
 *    3.2 将该结点的子结点压入队列
 *
 * }
 * */
/*
 * 函数名：levelOrder()
 * 输入：树（树的根结点）
 * 输出（返回值）：无
 * */
/*
 * 定义一个结构体
 * Queue
 * 操作：
 * 1.进队：Enqueue(Queue queue,ElementType data)
 * 2.出队：ElmentType Delqueue(Queue queue) 返回被删除的元素
 * 3.判断是否为空 IsEmpty(Queue queue)
 * 4.判断是否为满：IsFull(Queue queue)
 * 5.创建队列 Queue createQueue() 返回创建好的队列 Queue
 * */
/*typedef struct queue Queue;
typedef BTnode *ElementType2;
struct queue{
    ElementType2 data[MAXSIZE];
    int front,rear;
};
Queue *createQueue(){
    //分配空间
    Queue *queue=malloc(sizeof(Queue));
    //初始化参数
    queue->front=0;
    queue->rear=0;
    return queue;
}
//进队列
void Enqueue(Queue *queue,ElementType2 data){
    //1.先赋值
    queue->data[queue->rear]=data;
    //2.再移动
    queue->rear++;
}
ElementType2 Delqueue(Queue *queue){
    return queue->data[queue->front++];
}
int IsEmpty(Queue *queue){
    return queue->front==queue->rear;
}*/
//层序遍历
/*void levelOrder(BTnode *root){
    //1.创建队列
    Queue *queue=createQueue();
    //2.根结点进队
    Enqueue(queue,root);
    //3.开始循环
    BTnode *tmp;
    while(!IsEmpty(queue)){
        //3.1出队并打印
        //出队
        tmp=Delqueue(queue);
        //并打印
        printf("%c",tmp->data);
        //3.2被删除结点的子结点进队列
        if(tmp->left){
            Enqueue(queue,tmp->left);
        }
        if(tmp->right){
            Enqueue(queue,tmp->right);
        }
    }
}*/


//层序遍历
void levelOrder(BTnode *root){
    if(root==NULL)
        return;
    //1.创建队列
  //  Queue *queue=createQueue();
  BTnode *data[100];
  int front =0;
  int rear =0;
    //2.根结点进队
   // Enqueue(queue,root);
   data[rear++]=root;//插入 再移动
    //3.开始循环
    BTnode *tmp;
    while(front!=rear){
        //3.1出队并打印
        //出队
       tmp= data[front++];
        //tmp=Delqueue(queue);
        //并打印
        printf("%c",tmp->data);
        //3.2被删除结点的子结点进队列
        if(tmp->left){
           // Enqueue(queue,tmp->left);
           data[rear++]=tmp->left;
        }
        if(tmp->right){
            //Enqueue(queue,tmp->right);
            data[rear++]=tmp->right;
        }
    }
}


//求二叉树的高度
/*
 * 核心思想：整棵树的高度height=MAX[左子树的高度lf,右子树的高度lR]+1
 *
 * 函数名：getHeight()
 * 输入：树（树的根）
 * 输出：高度  返回值类型int
 * */
int getHeight(BTnode *root){
    //1.基线
    if(root==NULL)
        return 0;
    //2.调用自身 height=MAX[左子树的高度lf,右子树的高度lR]+1
   //return 1+getHeight(root->left)>getHeight(root->right)?getHeight(root->left):getHeight(root->right)
   int leftH=getHeight(root->left);//左子树的高度
   int rightH= getHeight(root->right);//右子树的高度
   if(leftH>rightH)
       return 1+leftH;
   else
       return 1+rightH;
}
//求二叉树的叶子结点数量
/*
 * 思想：整棵树的叶子数量=左子树的叶子数量+右子树的叶子数量
 *  叶子结点的判断： node.left==NULL&&node.right==NULL
 *
 *  函数名：leaf_count()
 *  输入：树（树的根）
 *  输出：数量 数值类型：int
 * */

int leaf_count(BTnode *root){
    //1.基线
    if(root==NULL)
        return 0;
    if(root->left==NULL&&root->right==NULL)
        return 1;
    //2.调用自身
    int left_leaf = leaf_count(root->left);//左子树的叶子数量
    int right_leaf = leaf_count(root->right);//右子树的叶子数量
    return left_leaf+right_leaf;

}
int main() {
    //1.创建结点并赋值
    BTnode *nodeA= createBTnode('A');
    BTnode *nodeB= createBTnode('B');
    BTnode *nodeD= createBTnode('D');
    BTnode *nodeF= createBTnode('F');
    BTnode *nodeI= createBTnode('I');
    BTnode *nodeL= createBTnode('L');
    //2.按照逻辑关系进行连接
    //2.1对根结点进行连接
    nodeA->left=nodeB;
    nodeA->right=nodeD;

    //对左子树进行连接
    nodeB->right=nodeF;
    nodeF->left=nodeL;

    //对右子树进行连接
    nodeD->left=nodeI;
    /*
     *          A
     *       /     \
     *      B       D
     *       \    /
     *        F  I
     *       /
     *      L
     * */
   // printf("Hello, World!\n");
    //printf("dta");
   inOrder(nodeA);
    printf("层序遍历：\n");
    levelOrder(nodeA);
    int h = getHeight(nodeA);
    printf("树的高度是%d",h);
    int leaf = leaf_count(nodeA);
    printf("树的叶子数量是：%d",leaf);

    return 0;
}
